<?php
//删除k个数字后的最小值
// 给出一个整数, 从该整数中去掉k个数字, 要求剩下的数字形成的新整数尽可能小. 这个整数可能超过了long的范围.
// 应该优先把高位的数字降低, 这样对新整数的值影响最大:
// 把原整数的所有数字从左到右进行比较, 如果发现某一位数字大于它右面的数字, 那么在删除该数字后, 必然会使该数位的值降低
// 这种依次求得局部最优解,最终得到全局最优解的思想, 叫做"贪心算法"

class RemoveKDigits {

    /**
     * 普通的解法, 用了两层循环, 每次都是从头开始循环
     * @param string $num 原整数
     * @param int $k 要删除数字的个数
     * @return string
     */
    public function do(string $num, int $k) {
        for ($i = 0; $i < $k; $i++) {
            $hasCut = false;
            //从左往右遍历, 找到比自己右侧数字大的数字并删除
            for ($j = 0; $j < strlen($num) - 1; $j++) {
                if (substr($num, $j, 1) > substr($num, $j + 1, 1)) {
                    $num = substr($num, 0, $j) . substr($num, $j + 1);
                    $hasCut = true;
                    break;
                }
            }
            //如果没有找到要删除的数字, 则删除最后一个数字
            if (!$hasCut) {
                $num = substr($num, 0, strlen($num) - 1);
            }
        }
        //清除整数左侧的数字0
        $start = 0;
        for ($j = 0; $j < strlen($num) - 1; $j++) {
            if (substr($num, $j, 1) != '0') {
                break;
            }
            $start++;
        }
        $num = substr($num, $start, strlen($num));
        //如果整数的所有数字都被删除了, 直接返回0
        if (strlen($num) == 0) {
            return 0;
        }

        return $num;
    }

    /**
     * 优化: 以遍历数字作为外循环, k作为内循环
     * @param string $num 原整数
     * @param int $k 要删除数字的个数
     * @return string
     */
    public function do2(string $num, int $k) {
        //新整数的最终长度 = 原整数长度 - k
        $newLength = strlen($num) - $k;
        //创建一个栈,用于接收所有的数字
        $stack = array_fill(0, strlen($num), '');
        $top = 0;
        for ($i = 0; $i < strlen($num); $i++) {
            //遍历当前数字
            $c = substr($num, $i, 1);
            //当栈顶数字大于遍历到的当前数字时, 栈顶数字出栈(相当于删除数字)
            while ($top > 0 && $stack[$top - 1] > $c && $k > 0) {
                $top--;
                $k--;
            }
            //遍历到的当前数字入栈
            $stack[$top++] = $c;
        }
        //找到栈中第一个非零数字的位置, 以此构建新的整数字符串
        $offset = 0;
        while ($offset < $newLength && $stack[$offset] == '0') {
            $offset++;
        }
        return $offset === $newLength ? '0' : implode('', array_slice($stack, $offset, $newLength - $offset));
    }

}

$m = new RemoveKDigits();
$arr = [
    ['num' => '1593212', 'k' => 3],
    ['num' => '30200', 'k' => 1],
    ['num' => '10', 'k' => 2],
    ['num' => '541270936', 'k' => 3],
];
foreach ($arr as $row) {
    echo $m->do($row['num'], $row['k']) . PHP_EOL;
    echo $m->do2($row['num'], $row['k']) . PHP_EOL;
}